package com.bubaiwantong.algorithms1.merge;

/**
 * @author bubaiwantong
 * @date 2022/12/8 0:32
 * @description this is a class file created by bubaiwantong in 2022/12/8 0:32
 */
public class MergeSort {


    public static void main(String[] args) {
        int[] arr = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        int[] tempArr = new int[10];
        MergeSort sort = new MergeSort();
        sort.print(arr);
        sort.sort(arr, tempArr, 0, arr.length - 1);
        sort.print(arr);
    }


    /**
     * 归并排序
     *
     * @param arr
     */
    public void sort(int arr[], int tempArr[], int begin, int end) {
        if (begin >= end) {
            return;
        }
        int mid = (begin + end) / 2;
        sort(arr, tempArr, begin, mid);
        sort(arr, tempArr, mid + 1, end);
        merge(arr, tempArr, begin, mid, end);
    }

    /**
     * 归并函数
     *
     * @param arr
     * @param tempArr
     * @param begin
     * @param end
     */
    public void merge(int arr[], int tempArr[], int begin, int mid, int end) {
        for (int i = begin; i <= end; i++) {
            tempArr[i] = arr[i];
        }

        int i = begin;
        int j = mid + 1;
        int k = begin;
        while (i <= mid && j <= end) {
            if (tempArr[i] < tempArr[j]) {
                arr[k++] = tempArr[i++];
            } else {
                arr[k++] = tempArr[j++];
            }
        }

        while (i <= mid) {
            arr[k++] = tempArr[i++];
        }

        while (j <= end) {
            arr[k++] = tempArr[j++];
        }

    }


    /**
     * 交换
     *
     * @param arr
     * @param i
     * @param j
     */
    public void swap(int arr[], int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 输出数组
     *
     * @param arr
     */
    public void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}
